package personal.leil.learning.exercises;

import personal.leil.learning.TreeNode;

/**
 * Created by Leil on 20.1.24
 */
public class LowestAncestor {


    /**
     * 使用二叉树DP的思路解决两个节点的最小公共祖先问题
     * <pre>
     * 解决思路如下：
     *     <ol>
     *         <li>可以看做是在每棵子树上递归向下找node1、node2节点的问题</li>
     *         <li>如果找到，则返回node1、node2</li>
     *         <li>如果一直向下未找到，则返回null</li>
     *         <li>
     *             查找后有如下几种两种情况：
     *             <ul>
     *                 <li>左右子树分别找到了node1和node2，则当前节点为最小公共祖先节点</li>
     *                 <li>左右子树只有其中一棵找到了node1或node2，则证明node1、node2在同一棵子树上互为祖先，则返回找到的node1或node2</li>
     *             </ul>
     *         </li>
     *     </ol>
     * </pre>
     *
     * @param root  根节点
     * @param node1 target node1
     * @param node2 target node2
     * @return lowest ancestor for node1 and node2
     */
    public static TreeNode lowestAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null) {
            return null;
        }
        if (root == node1 || root == node2) {
            return root;
        }
        TreeNode left = lowestAncestor(root.left, node1, node2);
        TreeNode right = lowestAncestor(root.right, node1, node2);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    /********************* For Test *************************/
    public static void main(String[] args) {
        TreeNode[] nodes = createSampleTree();
        TreeNode lowestAncestor = lowestAncestor(nodes[0], nodes[1], nodes[2]);
        System.out.println("lowest ancestor: " + lowestAncestor.value);
    }

    public static TreeNode[] createSampleTree() {
        /*
                    1
                   / \
                  2     3
                 / \   / \
                4   5  6   7
               /|   |       \
              8 9   10      11
                    / \
                   12  13
        */

        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;
        node7.right = node11;
        node10.left = node12;
        node10.right = node13;

        return new TreeNode[]{root, node9, node13};
    }


}
